#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i(a);i<=(b);++i)
#define req(i,a,b) for(int i(a);i>=(b);--i)
#define sort stable_sort
using namespace std;
char buf[1<<23],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<23,stdin),p1==p2)?EOF:*p1++)
template<typename TP> inline TP read(TP &num)
{
	TP x=0;
	int f=0;
	char ch=getchar();
	while(ch<48||ch>57) f|=ch=='-',ch=getchar();
	while(48<=ch&&ch<=57) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return num=f?-x:x;
}
template<typename ...Args> inline void read(Args &...args)
{
	(read(args),...);
}
template<typename TP> inline void write(TP x)
{
	(x<0)?(putchar('-'),x=-x):0;
	(x>9)?(write(x/10),0):0;
	putchar((x%10)^48);
}
template<typename TP> inline void writeln(TP x)
{
	write<TP>(x);
	puts("");
}
signed main()
{
	freopen("minimize.in","r",stdin);
	freopen("minimize.out","w",stdout);
	int n,c; read(n,c);
	vector<int> a(n);
	for(auto &x:a) read(x);
	if(is_sorted(a.begin(),a.end()))
	{
		vector<int> vals=a;
		vals.erase(unique(vals.begin(),vals.end()),vals.end());
		vector<int> pre(n); partial_sum(a.begin(),a.end(),pre.begin());
		int ans=1e18;
		for(auto val:vals)
		{
			int pos=lower_bound(a.begin(),a.end(),val)-a.begin();
			int cost=val*pos-pre[pos-1]+(n-1-pos)*c;
			ans=min(ans,cost);
		}
		writeln(ans),exit(0);
	}
	if(!c) return puts("0"),0;
	if(n<=1000)
	{
		auto f=[&](int x,int y)->int{return x>=y?x-y:c;};
		vector<int> sa=a; sort(sa.begin(),sa.end());
		vector<vector<int>> dp(n,vector<int>(n));
		rep(j,0,n-1) dp[0][j]=f(sa[j],a[0]);
		rep(i,1,n-1)
		{
			vector<int> ms(n);
			ms[n-1]=dp[i-1][n-1];
			req(j,n-2,0) ms[j]=min(ms[j+1],dp[i-1][j]);
			rep(j,0,n-1) dp[i][j]=f(sa[j],a[i])+ms[j];
		}
		int ans=1e18;
		rep(j,0,n-1) ans=min(ans,dp[n-1][j]);
		writeln(ans),exit(0);
	}
	auto evaluate=[&](const vector<int> &arr)->int
	{
		int res=0;
		rep(i,0,n-1) res+=arr[i]>=a[i]?arr[i]-a[i]:c;
		return res;
	};
	vector<int> cur=a; sort(cur.begin(),cur.end(),greater<>());
	int mx=cur[0],mn=cur.back();
	vector<int> best=cur;
	int best_val=evaluate(cur),cur_val=best_val;
	long double temp=1e12; mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
	while(temp>1e-12&&clock()<4.9*CLOCKS_PER_SEC)
	{
		int idx=rnd()%n;
		vector<int> nxt=cur;
		int ub=!idx?mx:nxt[idx-1],lb=idx==n-1?mn:nxt[idx+1];
		auto random_range=[&](int l,int r)->int{return rnd()%(r-l+1)+l;};
		int to=random_range(lb,ub); nxt[idx]=to;
		int nxt_val=evaluate(nxt),dt=nxt_val-cur_val;
		if(dt<0||exp(-dt/temp)>rnd()/4294967295.0) cur=nxt,cur_val=move(nxt_val),best_val=min(best_val,cur_val);
		temp*=0.99999;
	}
	writeln(best_val);
	return 0;
}
